Longest substring with at least k repeating characters

Time: O(N); Space: O(1); medium

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input: s = “aaabb”, k = 3

Output: 3

Explanation:

  • The longest substring is “aaa”, as ‘a’ is repeated 3 times.

Example 2:

Input: s = “ababbc”, k = 2

Output: 5

Explanation:

  • The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.

[2]:

class Solution1(object):
    """
    Time: O(26*N)=O(N)
    Space: O(26)=O(1)
    """
    def longestSubstring(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        def longestSubstringHelper(s, k, start, end):
            count = [0] * 26
            for i in range(start, end):
                count[ord(s[i]) - ord('a')] += 1

            max_len = 0
            i = start
            while i < end:
                while i < end and count[ord(s[i]) - ord('a')] < k:
                    i += 1
                j = i
                while j < end and count[ord(s[j]) - ord('a')] >= k:
                    j += 1

                if i == start and j == end:
                    return end - start

                max_len = max(max_len, longestSubstringHelper(s, k, i, j))
                i = j
            return max_len

        return longestSubstringHelper(s, k, 0, len(s))

[8]:

sol = Solution1()
s = "aaabb"
k = 3
assert sol.longestSubstring(s, k) == 3
s = "ababbc"
k = 2
assert sol.longestSubstring(s, k) == 5